1. Field of the Invention
The present invention relates to cryptography systems and methods, and particularly to a system and method for securing scalar multiplication against simple power attacks.
2. Description of the Related Art
Elliptic Curve Cryptosystems (ECC), originally proposed by Niel Koblitz and Victor Miller in 1985, offer a serious alternative to earlier public key cryptosystems, such as Rivest-Shamir-Adleman (RSA) and ElGamal, with much shorter key size. To date, no significant breakthroughs have been made in determining weaknesses in the ECC algorithm, which is based on the discrete logarithm problem over points on an elliptic curve. The fact that the problem appears so difficult to crack means that key sizes can be reduced considerably, even exponentially. This has caused ECC to become a serious challenger to RSA and ElGamal cryptosystems. Because of these advantages, ECC have been recently incorporated in many standards. ECC have gained popularity for cryptographic applications because of the short key, and are considered to be particularly suitable for implementation on smart cards or mobile devices.
An elliptic curve over a finite field GF(q) defines a set of points (x, y) that satisfy the elliptic curve equation together with the point O, known as the “point at infinity”. The “point at infinity” does not satisfy the elliptic curve equation. The coordinates x and y of the elliptic curve points are elements of the field GF(q), where q=pm and p is prime.
Equations (1) and (2) define the elliptic curve equations for the fields GF(p) and GF(2m), respectively:y2=x3+ax+b  (1)where a,bεGF(p) and 4a+27b2≠0 (mod p); andy2+xy=x3+ax2+b  (2)where a, bεGF(2m) and b≠0.
The set of discrete points on an elliptic curve form an abelian group (commutative group), whose group operation is known as point addition. Bounds for the number of discrete points n on an elliptic curve over a finite field GF(q) are defined by Hasse's theorem, given in Equation (3), where the symbol n represents the number of points on the elliptic curve and where q=pm represents the number of elements in the underlying finite field:q+1−2√{square root over (q)}≦n≦1+1+2√{square root over (q)}.  (3)
Elliptic curve “point addition” is defined according to the “chord-tangent process”. Point addition over GF(p) is described as follows: Let P and Q be two distinct points on an elliptic curve E defined over the real numbers with Q≠−P (Q is not the additive inverse of P). The addition of P and Q is the point R=P+Q, where R is the additive inverse of S , and S is a third point on the elliptic curve intercepted by the straight line through points P and Q. For the curve under consideration, R is the reflection of the point S with respect to the x-axis, that is, if R is the point (x, y), then S is the point (x, −y).
When P=Q and P≠−P, the addition of P and Q is the point R, where R=2P and R is the additive inverse of S, and S is the third point on the elliptic curve intercepted by the straight line tangent to the curve at point P. This operation is referred to as “point doubling”.
The “point at infinity”, O, is the additive identity of the group. The most relevant operations involving O are the following: the addition of a point P and O is equal to P (i.e., P+O=P); and the addition of a point P and its additive inverse, −P, is equal to O (i.e., P−P=O). If P is a point on the curve, then −P is also a point on the curve.
The point operation used by elliptic curve cryptosystems is referred to as point multiplication. This operation is also referred to as scalar point multiplication. The point multiplication operation is denoted as kP, where k is an integer number and P is point on the elliptic curve. The operation kP represents the addition of k copies of point P, as shown in Equation (4) below:
                    kP        =                                            P              +              P              +              …              +              P                                      ︸                              k                ⁢                                                                  ⁢                times                ⁢                                                                  ⁢                P                                              .                                    (        4        )            
Elliptic curve cryptosystems are built over cyclic groups. Each group contains a finite number of points, n, that can be represented as scalar multiples of a generator point: iP for i=0, 1, . . . , n−1, where P is a generator of the group. The order of point P is n, which implies that nP=O and iP≠O for 1<i<n−1. The order of each point on the group must divide n. Consequently, a point multiplication kQ for k>n can be computed as (k mod n)Q.
Scalar multiplication is the basic operation for ECC. Scalar multiplication in the group of points of an elliptic curve is the analogue of exponentiation in the multiplicative group of integers modulo a fixed integer m. Computing kP can be performed using a straightforward double-and-add approach based on the binary representation of k=kl−1, . . . , k0 where kl−1 is the most significant bit of k. Other scalar multiplication methods have been proposed in the literature.
One of the simplest scalar multiplication algorithms is the double-and-add point multiplication algorithm, which is the so-called binary algorithm. Algorithm 1 and 2 show two such double-and-add scalar multiplication algorithms, respectively. The algorithms inspect the multiplier k . For each inspected bit, the algorithms perform a point double, and if the inspected bit is one, the algorithms also perform a point add:
Algorithm 1: Double-and-AddInputs: P,kOutput: kPInitialization:  Q[0] = 0; Q[1] = PScalar Multiplication:  for i = 0 to m−1     if ki = 1 then Q[0] = ADD(Q[0],Q[1])    Q[1] = DBL(Q[1])  end forreturn Q[0]
Algorithm 2: Double-and-Add-AlwaysInputs: P,kOutput: kPInitialization:  Q[0] = P; Q[1] = 0; Q[2] = PScalar Multiplication:  for i = 0 to m−1    Q[1] = Q[1+ki]    Q[0] = DBL(Q[0])    Q[2] = ADD(Q[0],Q[1])  end forreturn Q[1]
In the above algorithms, the “DBL” operation is a simple point doubling operation; e.g., Q[1]=DBL(Q[1]) simply means updating Q[1] as Q[1]=2Q[1]. Similarly, the “ADD” operation is a simple point adding operation; e.g., Q[0]=ADD(Q[0],Q[1]) simply means updating Q[0] as Q[0]=Q[0]+Q[1]. As noted above, kP can be computed using a straightforward binary method based on the binary expression of multiplier k. A conventional prior art scalar multiplication method for elliptic cryptosystems is shown in the U.S. Patent Application Publication No. 2009/0214023, which is hereby incorporated by reference in its entirety.
The binary scalar multiplication method shown in Algorithm 1 is the most straightforward scalar multiplication method. It inspects the bits of the scalar multiplier k, and if the inspected bit ki=0, only point doubling is performed. If, however, the inspected bit ki=1, both point doubling and point addition are performed. The binary method requires m point doublings and an average of m/2 point additions.
Power analysis attacks are usually divided into two types: Simple Power Analysis (SPA) attacks and Differential Power Analysis (DPA) attacks. SPA attacks consist of observing the power consumption during a single execution of a cryptographic algorithm. The power consumption analysis may also enable one to distinguish between point addition and point doubling. In the “double-and-add-always” algorithm, shown in Algorithm 2, the point addition and point doubling are performed in each loop iteration, where the result of the point addition operation may be either accepted or ignored based on the ki value.
The disadvantage of the double-and-add-always algorithm is the added dummy point additions. Algorithm 2 requires m−1 point doublings and m−1 point additions. It would be desirable to provide an effective countermeasure against SPA attacks in elliptic curve cryptosystems which requires no such additional computational overhead.
Thus, a system and method for securing scalar multiplication against simple power attacks solving the aforementioned problems is desired.